//
//  DNode.hpp
//  408数据结构
//
//  Created by Cai Yuanhao on 2022/3/25.
//

#ifndef DNode_hpp
#define DNode_hpp

#include <stdio.h>
#include <stdlib.h>

#endif /* DNode_hpp */

typedef int ElemType;

typedef struct DNode{
    ElemType data;
    struct DNode *prior,*next;
}DNode,*DLinkList;

DLinkList initDLinkList(DLinkList &L){
    L=(DLinkList)malloc(sizeof(DNode));
    L->next=L->prior=NULL;
    return L;
}
int getLen(DLinkList L){
    if (L->next==NULL) {
        return 0;
    }
    int i=1;
    L=L->next;
    while (L->next!=NULL) {
        i++;
        L=L->next;
    }
    return i;
}
//头插法新建双链表
DLinkList List_HeadCreate(DLinkList &L){
    DNode *s;
    int x;
    L=initDLinkList(L);
    scanf("%d",&x);
    while (x!=9999) {
        s=(DLinkList)malloc(sizeof(DNode));
        s->data=x;
        s->next=L->next;
        s->prior=L;
        L->next=s;
        scanf("%d",&x);
    }
    return L;
}
void printlist(DLinkList l){
    l=l->next;
    do {
        printf("%d ",l->data);
        l=l->next;
    } while (l);
    printf("\n");
}


//尾插法建立单链表
DLinkList List_TailCreate(DLinkList &L){
    L=initDLinkList(L);
    DNode *s,*r=L;
    int x;
    scanf("%d",&x);
    while (x!=9999) {
        s=initDLinkList(s);
        s->data=x;
        s->prior=r;
        r->next=s;
        r=s;
        scanf("%d",&x);
    }
    r->next=NULL;
    return L;
}
//按序号取值
DNode *GetElem(DLinkList L,int i){
    int j = 1;
    DLinkList p=L->next;
    if (i==0) {
        return L;
    }
    if (i<1) {
        return NULL;
    }
    while (p&&j<i) {
        p=p->next;
        j++;
    }
    return p;
}
//插入结点
bool LinkList_Insert(DLinkList L,int loc,ElemType e){
    if (loc<1||loc>getLen(L)) {
        return false;
    }
    DLinkList p=GetElem(L, loc-1);
    DLinkList s=(DLinkList)malloc(sizeof(DNode));
    s->data=e;
    s->next=p->next;
    p->next->prior=s;
    s->prior=p;
    p->next=s;
    return true;
}
bool delDnode(DLinkList &L,int loc){
    if (loc<1||loc>getLen(L)) {
        return false;
    }
    DLinkList p=GetElem(L, loc-1);
    DLinkList q=p->next;
    p->next=q->next;
    q->next->prior=p;
    free(q);
    return true;
}

